package com.leetcode;

import java.util.*;

/**
 * 126. 单词接龙 II
 * TODO: 待研究图的算法
 */
public class Solution126 {

    Map<String, Integer> wordId = new HashMap<>();
    Map<Integer, String> idWord = new HashMap<>();
    List<List<Integer>> edge = new ArrayList<>();
    int nodeNum = 0;

    public List<List<String>> findLadders(String beginWord,
                                          String endWord,
                                          List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return res;
        }
        int[] dist = new int[nodeNum];
        Arrays.fill(dist, Integer.MAX_VALUE);

        int[] from = new int[nodeNum];
        Arrays.fill(from, -1);

        int beginId = wordId.get(beginWord);
        int endId = wordId.get(endWord);
        dist[beginId] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginId);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == endId) {
                res.add(genPath(endId, from));
            }
            for (Integer it : edge.get(node)) {
                if (dist[it] == Integer.MAX_VALUE) {
                    dist[it] = dist[node] + 1;
                    from[it] = node;
                    queue.offer(it);
                }
            }
        }
        return res;
    }

    private List<String> genPath(int endId, int[] from) {
        List<String> path = new ArrayList<>();
        Deque<Integer> stack = new LinkedList<>();
        int p = endId;
        while (p != -1) {
            if (!idWord.get(p).contains("*")) {
                stack.push(p);
            }
            p = from[p];
        }
        while (!stack.isEmpty()) {
            path.add(idWord.get(stack.pop()));
        }
        return path;
    }

    private void addEdge(String word) {
        addWord(word);
        int id = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; i++) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int newId = wordId.get(newWord);
            edge.get(id).add(newId);
            edge.get(newId).add(id);
            array[i] = tmp;
        }
    }

    private void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum);
            idWord.put(nodeNum, word);
            nodeNum++;
            edge.add(new ArrayList<>());
        }
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList<String>() {
            {
                add("hot");
                add("dot");
                add("dog");
                add("lot");
                add("log");
                add("cog");
            }
        };
        List<List<String>> res = new Solution126().findLadders(beginWord, endWord, wordList);
        System.out.println(res);
    }

}

